/**线性链表（单链表）
1. 实现单链表核心操作：
从数组创建链表、头插 / 尾插节点、删除所有值为 x 的节点、反转链表（非递归）、求链表长度。
测试用例：链表 1->2->3->2->4，删除值为 2 的节点后变为 1->3->4；反转后变为 4->3->1。
2. 设计函数找到单链表的中间节点（若长度为偶数取第 n/2 个），
并判断链表是否为回文结构（如 1->2->3->2->1 是回文，1->2->3->4 不是）。
3. 实现两个非递减单链表的合并（合并后仍为非递减）：输入 1->3->5 和 2->4->6，输出
1->2->3->4->5->6。
本套试题由曹婷老师根据元宇宙平台非凡就业班课程内容整理 */
#include <stdio.h>
#include <stdlib.h>


// 单链表节点定义
typedef struct ListNode
{
    int val;               // 节点值
    struct ListNode *next; // 指向下一节点的指针
} ListNode, Node;

// 1. 核心操作函数声明
// 从数组创建链表（arr为数组，n为数组长度）
ListNode *createListFromArray(int *arr, int n);

// 头插节点（在链表头部插入值为val的节点，返回新链表头）
ListNode *insertAtHead(ListNode *head, int val);

// 尾插节点（在链表尾部插入值为val的节点，返回原链表头，若原链表为空则返回新节点）
ListNode *insertAtTail(ListNode *head, int val);

// 删除所有值为x的节点（返回处理后的链表头）
ListNode *deleteAllX(ListNode *head, int x);

// 非递归方式反转链表（返回反转后的新头）
ListNode *reverseList(ListNode *head);

// 求链表长度（返回节点个数）
int getListLength(ListNode *head);

// 2. 中间节点与回文判断函数
// 找到链表中间节点（长度为偶数时取第n/2个，n为长度）
ListNode *findMiddleNode(ListNode *head);

// 判断链表是否为回文结构（是返回1，否返回0）
int isPalindrome(ListNode *head);

// 3. 合并两个非递减链表（返回合并后的新链表头）
ListNode *mergeTwoSortedLists(ListNode *l1, ListNode *l2);

//遍历
void printLinkList(ListNode* L);

//----------------------------------------------------------------

// 从数组创建链表（arr为数组，n为数组长度）  (已修改)！！！！！！！！！！！！
ListNode *createListFromArray(int *arr, int n)
{
   ListNode *head = NULL;
    for (int i = 0; i < n; i++){
       head = insertAtTail(head, arr[i]);
    }

    return head;
}

// 头插节点（在链表头部插入值为val的节点，返回新链表头）！！头插，就别管head NULL了，直接创建
ListNode *insertAtHead(ListNode *head, int val)//（已修改）！！！！！！！！！！！！
{
    // 1. 只创建1个新节点，统一处理所有情况
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    if (newNode == NULL)
    {
        exit(1); // 内存分配失败
    }

    // 2. 新节点的值赋值，next指向原头节点
    newNode->val = val;
    newNode->next = head; // 空链表时head为NULL，新节点next也为NULL，逻辑自洽

    // 3. 新节点成为新的表头，直接返回
    return newNode;
}

// 尾插节点（在链表尾部插入值为val的节点，返回原链表头，若原链表为空则返回新节点）
// 尾插节点（在链表尾部插入值为val的节点，返回原链表头，若原链表为空则返回新节点）
ListNode *insertAtTail(ListNode *head, int val)
{
    // 创建新节点（统一使用ListNode*）
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    if (node == NULL)  // 合并内存检查，避免重复代码
    {
        exit(1);
    }
    node->val = val;
    node->next = NULL;

    // 若原链表为空，直接返回新节点
    if (head == NULL)
    {
        return node;
    }

    // 找到链表尾部并插入新节点
    ListNode *temp = head;
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = node;

    return head;
}

// 删除所有值为x的节点（返回处理后的链表头）   （已经修改）！！！！！！！！！！
ListNode *deleteAllX(ListNode *head, int x)
{
    // if (head == NULL)
    // {
    //     exit(NULL);
    // }
    Node *dummy = (Node *)malloc(sizeof(Node)); // 重要！！！！！！！！！！！！！！！！
    dummy->next = head;
    Node *temp = dummy;
    while (temp->next != NULL)
    {
        if (temp->next->val == x)
        {
            Node *n = temp->next;
            temp->next = temp->next->next;
            free(n);
        }
        else
        {
            temp = temp->next;
        }
    }
    Node *newhead = dummy->next;//！！！！！！！！！！！！！！
    free(dummy);

    return newhead;
}

// 求链表长度（返回节点个数）  （正确！！！！！）
int getListLength(ListNode *head)
{
    int count = 0;
    Node *temp = head;
    while (temp != NULL)
    {
        count++;
        temp = temp->next;
    }
    return count;
}

// 非递归方式反转链表（返回反转后的新头）(头节点存了元素)  正确！！！！！
ListNode *reverseList(ListNode *head)
{ // head 1 2 3

    /**  有哨兵头节点
    Node* p = head->next->next;
    Node* q = NULL;
    head->next->next=NULL;;
    while(p!=NULL){
        q=p;
        p=p->next;
        q->next=head->next;
        head->next=q;
    }*/
    // 无哨兵头节点
    Node *prev = NULL;
    Node *cur = head;
    Node *next = NULL;
    while (cur != NULL)
    { // 1 2 3 4
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

// 2. 中间节点与回文判断函数
// 找到链表中间节点（长度为偶数时取第n/2个，n为长度）  （已修改）！！！！！！！！！！！！！
ListNode *findMiddleNode(ListNode *head)
{
    Node *fast = head;
    Node *slow = head;
    while (fast->next!= NULL && fast->next->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

// 判断链表是否为回文结构（是返回1，否返回0） ！！！！（已修改）
int isPalindrome(ListNode *head) {
    if (head == NULL || head->next == NULL) return 1; // 空或单节点是回文
    //反转后链表被破坏了！！！！！！！！！！！！！！！！
    // 1. 找到中间节点 !!!!!!!!!!
    ListNode *mid = findMiddleNode(head);
    // 2. 反转后半段（从mid->next开始，不影响前半段）!!!!!!!
    ListNode *secondHalf = reverseList(mid->next);
    // 3. 比较前半段和反转后的后半段
    ListNode *p1 = head;
    ListNode *p2 = secondHalf;
    int isPalin = 1;

    while (p2 != NULL) { // 反转后 后半段长度 <= 前半段 ！！！！！！
        if (p1->val != p2->val) {
            isPalin = 0;
            break;
        }
        p1 = p1->next;
        p2 = p2->next;
    }

    // 4. 恢复链表（可选）
    mid->next = reverseList(secondHalf);
    return isPalin;
}

// 3. 合并两个非递减链表（返回合并后的新链表头）
ListNode *mergeTwoSortedLists(ListNode *l1, ListNode *l2)
{
    Node *head = (Node *)malloc(sizeof(Node));
    Node *temp_head = head;
    Node *temp_l1 = l1;
    Node *temp_l2 = l2;
    while (temp_l1 != NULL && temp_l2 != NULL)
    {
        if (temp_l1->val < temp_l2->val)
        {
            temp_head->next = temp_l1;
            temp_l1 = temp_l1->next;
        }
        else
        {
            temp_head->next = temp_l2;
            temp_l2 = temp_l2->next;
        }
        temp_head = temp_head->next; //!!!!!!!!!!!!!!!!!!!!!
    }
    if (temp_l1 != NULL)
    {
        temp_head->next = temp_l1;
    }
    else
    {
        temp_head->next = temp_l2;
    }
    Node *newhead = head->next; //!!!!!!!!!!!!!!!!不要用temp_head避免阅读不理解
    free(head);
    return newhead;
}
//打印 （已修改）
void printLinkList(ListNode* L){
    if (L == NULL)
    {
        printf("空链表\n");
        return;
    }
    Node* temp =L;
    while(temp!=NULL)
    {
        // 最后一个节点不打印箭头
        if (temp->next != NULL)
        {
            printf("%d -> ", temp->val);
        }
        else
        {
            printf("%d\n", temp->val);
        }
        temp = temp->next;
    }

}

// 测试
/**测试用例：链表 1->2->3->2->4，删除值为 2 的节点后变为 1->3->4；反转后变为 4->3->1。 */
void Ltest1()
{
    int arr[] = {1,2,3,2,4};
    Node* L = createListFromArray(arr,5);
    printf("数组生成链表链表 1->2->3->2->4\n");
    printLinkList(L);
    L = deleteAllX(L,2);
    printf("删除值为 2 的节点后变为 1->3->4\n");
    printLinkList(L);
    printf("反转后变为 4->3->1\n");
    printLinkList(reverseList(L));
}

/**
 * 2. 设计函数找到单链表的中间节点（若长度为偶数取第 n/2 个），
并判断链表是否为回文结构（如 1->2->3->2->1 是回文，1->2->3->4 不是）。
 * */
void Ltest2(){
    int arr[]={1,2,3,2,1};
    Node* L = createListFromArray(arr,5);
    printf("数组生成链表 1->2->3->2->1\n");
    printLinkList(L);
    if(isPalindrome(L)){
        printf("是回文\n");
    }else{
        printf("不是回文\n");
    }
}
/**3. 实现两个非递减单链表的合并（合并后仍为非递减）：输入 1->3->5 和 2->4->6，输出
1->2->3->4->5->6。*/
void Ltest3(){
    int arr1[]={1,3,5};
    int arr2[]={2,4,6};
    Node* L1 = createListFromArray(arr1,3);
    Node* L2 = createListFromArray(arr2,3);
    printf("数组生成链表 1->3->5 和 2->4->6\n");
    printLinkList(L1);
    printLinkList(L2);
    printf("合并后为 1->2->3->4->5->6\n");
    printLinkList(mergeTwoSortedLists(L1,L2));
}
int main(){
    Ltest1();
    Ltest2();
    Ltest3();
}